package leetcode;

public class RegularExpression {

	public static void main(String[] args) {
		RegularExpression object = new RegularExpression();
		String string = "bbabba";
//		String pattern = ".*a*a";
//		System.out.println(object.isMatch(string, pattern));
		
		String pattern = "*z";
		System.out.println(object.wildcardIsMatch(string, pattern));
	}
	
	public boolean isMatch(String s, String p) {
		if(s == null || p == null){
			return s == p;
		}
        char[] chars = s.toCharArray();
        char[] pattern = p.toCharArray();
        return process(chars, pattern, 0, 0);
    }
	
	//判断s[sIndex...length - 1] 跟p[pIndex...length - 1]是否匹配
	
	//有大量冗余判断, RunTime 48ms
	public boolean process(char[] s, char[] pattern, int sIndex, int pIndex){
		if(pIndex == pattern.length){
			return sIndex == s.length;
		}
		//首先判断下一个字符是否是*,如果不是
		if(pIndex + 1 >= pattern.length || pattern[pIndex + 1] != '*'){
			return sIndex != s.length && (s[sIndex] == pattern[pIndex] || pattern[pIndex] == '.')
					&& process(s, pattern, sIndex + 1, pIndex + 1);
		}
		//如果下一个字符是*
		while(sIndex != s.length &&(s[sIndex] == pattern[pIndex] || pattern[pIndex] == '.')){
			//pattern跳过*
			//这里为什么不传sIndex + 1呢
			//即使相等，比如a 与 a*a , 我们也需要判断a*匹配0个的情况
			//所以我们首先判断sIndex,之后sIndex++，说明匹配1、2、3...的情况
			if(process(s, pattern, sIndex, pIndex + 2)){
				return true;
			}
			sIndex++;
		}
		//如果当前字符不能与pattern匹配，比如ab 与 c*a*b*, a与c*不匹配
		return process(s, pattern, sIndex, pIndex + 2);
	}
	
	//由于递归过程中, 只有sIndex和pIndex在变化，所以我们可以使用动态规划
	//RunTime 38ms
	public boolean isMatchDP(String s, String p){
		if(s == null || p == null){
			return s == p;
		}
		char[] chars = s.toCharArray();
		char[] pattern = p.toCharArray();
		boolean[][] dp = initDP(chars, pattern);
		
		for(int i = chars.length - 1; i >= 0; i--){
			for (int j = pattern.length - 2; j >= 0; j--) {
				if(pattern[j + 1] != '*'){
					dp[i][j] = (chars[i] == pattern[j] || pattern[j] == '.') &&
							dp[i + 1][j + 1];
				}else{
					int sTemp = i;
					while(sTemp != chars.length && (chars[i] == pattern[j] || pattern[j] == '.')){
						if(dp[sTemp][j + 2]){
							dp[i][j] = true;
							break;
						}
						sTemp++;
					}
					//如果不匹配
					if(!dp[i][j]){
						dp[i][j] = dp[sTemp][j + 2];
					}
				}
			}
		}
		return dp[0][0];
	}

	private boolean[][] initDP(char[] chars, char[] pattern) {
		int sLength = chars.length;
		int pLength = pattern.length;
		//dp[i][j]表示str[i ... sLength - 1]是否匹配pattern[j ... pLength - 1]
		boolean[][] dp = new boolean[sLength + 1][pLength + 1];
		//两个都是空时是匹配的
		dp[sLength][pLength] = true;
		//初始化dp[sLength][0 ... pLength - 1]
		//什么情况下""匹配pattern是true呢，就是pattern是 X*这样
		for(int j = pLength - 2; j >= 0; j = j - 2){
			if(pattern[j] != '*' && pattern[j + 1] == '*'){
				dp[sLength][j] = true;
			}else{
				//一旦找到不符合的，我们就可以断定前面的肯定不可能匹配，直接break
				//比如"" 与 "a*aa*a*a*"
				break;
			}
		}
		//由于空字符串与任何非空的不匹配，所以dp[0...sLength - 1][pLength]全部为false
		
		//由于我们是从dp[][pLength - 2]开始计算的，我们还需要初始化dp[][pLength - 1]
		//最后一个字符只匹配相等的或者最后一个字符为.匹配全部
		if(sLength > 0 && pLength > 0){
			if(pattern[pLength - 1] == '.' || pattern[pLength - 1] == chars[sLength - 1]){
				dp[sLength - 1][pLength - 1] = true;
			}
		}
		return dp;
	}
	
	
	//通配符匹配：
	// '?' Matches any single character.
	// '*' Matches any sequence of characters(including the empty sequence).
	//比如aa 匹配 *为true，注意与正则表达式的不同之处.
	//isMatch("aab", "c*a*b") → false
	
	// Runtime: 154 ms, beat 6.52%
	public boolean wildcardIsMatch(String s, String p) {
		if(s == null || p == null){
			return s == p;
		}
		char[] chars = s.toCharArray();
		char[] pattern = p.toCharArray();
		//同样，dp[i][j]表示的是chars[i ... length - 1]是否与chars[j...length - 1]匹配
		boolean[][] dp = initWildcardDP(chars, pattern);
		
		for(int i = chars.length - 1; i >= 0; i--){
			for (int j = pattern.length - 1; j >= 0; j--) {
				if(pattern[j] != '*'){
					dp[i][j] = (chars[i] == pattern[j] || pattern[j] == '?') &&
							dp[i + 1][j + 1];
				}else{
					int sTemp = i;
					while(sTemp <= chars.length){
						if(dp[sTemp][j + 1]){
							dp[i][j] = true;
							break;
						}
						sTemp++;
					}
				}
			}
		}
		return dp[0][0];
    }

	private boolean[][] initWildcardDP(char[] chars, char[] pattern) {
		int sLength = chars.length;
		int pLength = pattern.length;
		//dp[i][j]表示str[i ... sLength - 1]是否匹配pattern[j ... pLength - 1]
		boolean[][] dp = new boolean[sLength + 1][pLength + 1];
		// 两个都是空时是匹配的
		dp[sLength][pLength] = true;
		// 初始化dp[sLength][0 ... pLength - 1]
		// 什么情况下""匹配pattern是true呢，就是pattern是 X*这样
		for (int j = pLength - 1; j >= 0; j--) {
			//*能够匹配空字符串
			if (pattern[j] == '*') {
				dp[sLength][j] = true;
			} else {
				// 一旦找到不符合的，我们就可以断定前面的肯定不可能匹配，直接break
				// 比如"" 与 "aa*z**"
				break;
			}
		}
		return dp;
	}
	
	
}
